package com.example.arithmeticleetcode.learnArithmetic2.dynamic_programming;

/**
 * @program: arithmetic-leetcode
 * @description: 最长上升子序列
 * @author: FangZhen
 * @create: 2020-12-18 13:33
 **/
public class LTS {

    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 2, 5, 3, 7, 101, 18};
        System.out.println(lengthOfLIS(nums));
        System.out.println(lengthOfLIS2(nums));
        System.out.println(lengthOfLIS3(nums));

    }

    /**
     * 二分搜索 牌堆 O(nlogn)
     *
     * @param nums
     * @return
     */
    public static int lengthOfLIS3(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        //牌堆的数量
        int len = 0;
        //牌顶数组
        int[] top = new int[nums.length];
        //遍历所有的牌
        for (int num : nums) { //n
           int begin = 0;
           int end = len;
           while (begin < end) {
               int mid = (begin + end) >> 1; //logN
               if (num <= top[mid]) {
                    end = mid;
               } else {
                   begin = mid + 1;
               }
           }
           top[begin] = num;
           if (begin == len) len++;
        }
        return len;
    }

    /**
     * 牌堆 O(N^2)
     *
     * @param nums
     * @return
     */
    public static int lengthOfLIS2(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        //牌堆的数量
        int len = 0;
        //牌顶数组
        int[] top = new int[nums.length];
        //遍历所有的牌
        for (int num : nums) {
            int j = 0;
            while (j < len) {
                //如果牌顶数组大于等于当前牌
                if (top[j] >= num) {
                    top[j] = num;
                    break;
                }
                //遍历下一个牌堆比较
                j++;
            }
            //要开辟新的牌堆
            if (j == len) {
                top[j] = num;
                len++;
            }
        }
        return len;
    }

    /**
     * 动态规划 时间复杂度O(N^2) 空间复杂度O(N)
     *
     * @param nums
     * @return
     */
    public static int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        int max = dp[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] <= nums[j]) continue;
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            max = Math.max(dp[i], max);
        }
        return max;
    }
}
